package Test;

/**
 * @author Kevin
 * @date 2020/3/5 21:53
 */
public class Bag {
    private int[] weight = new int[]{2, 2, 4, 6, 3}; //物品的重量
    private int n = 5; //物品个数
    private int w = 9; //背包承重
    private int maxW = Integer.MIN_VALUE; //结果放到maxW中

    public int knapsack(int[] weight, int n, int w) {
        boolean[][] states = new boolean[n][w+1];
        states[0][0] = true;
        if (weight[0] < w) {
            states[0][weight[0]] = true;
        }
        for (int i = 1; i < n; i++) {//动态规划状态转移
            for (int j = 0; j < w; j++) {// 不把第i个物品放入背包
                if (states[i-1][j] == true) states[i][j] = states[i-1][j];
            }
            for (int j = 0; j < w-weight[i]; j++) states[i-1][j+weight[i]] = true;
        }
        return 0;
    }

    public static int knapsack2(int[] items, int n, int w) {
        boolean[] states = new boolean[w + 1];
        states[0] = true;
        if (items[0] <= w) {
            states[items[0]] = true;
        }
        for (int i = 1; i < n; i++) {
            //j 需要从大到小来处理。如果我们按照 j 从小到大处理的话，会出现 for 循环重复计算的问题
            for (int j = w - items[i]; j >= 0; j--) {
                if (states[j] == true) states[j+items[i]] = true;
            }
        }
        return 0;
    }
}
